/*
此代码的功能：
遍历前 10001 个素数，并输出第 10001 个素数是多少：
此代码的思想：从 5 开始，只有 6x-1 和 6x+1 有可能是素数
6x+2 = 2(3x+1)
6x+3 = 3(2x+1)
6x+4 = 2(3x+2)
6x-1 = 6(x-1)+5
所以 n % 6 =1 或者 n % 6 = 5 这两个可能是素数
判断 6x+1 是否是素数的方法：让 6x+1 对小于 math.sqrt(6x+1) 所有的质数取模，如果都不等0就表示是质数。
这里说明下为什么是 math.sqrt(6x+1),这个源于求质数的另一个方法：n 对 2 - math.sqrt(n) 这些整数取模，如果都不等于0，就表示n 是素数
现在的问题就是如何确定小于 math.sqrt(6x+1) 所有的质数。
从100 以内的质数中发现规律：
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
从中可以得到一个规律：
(5.to(math.sqrt(6x=1),6)) 构造一个数列，从 5 开始，步长为 6，最大值为 math.sqrt(6x+1) 这个数列中的所有数字都是质数。
同样构造另一个数列，从7(5+2=7)开始，步长为 6 ，最大值为 math.sqrt(6x+1) 这个数列中的所有数字都是质数
将上述两个队列合并后就变成小于 math.sqrt(6) 的所有质数
*/
import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks

object prime {
  def main(args: Array[String]): Unit = {

    val n = 1000001
    val primeArrayBuffer = ArrayBuffer[Int](2,3)
    val breakLoop = new Breaks
    breakLoop.breakable {
      for (i <- 2 to n) {
        val flage = isPrime(i)
        if (flage) {
          primeArrayBuffer += i
        }
        if (primeArrayBuffer.size > 10000) {
          println(primeArrayBuffer.last)
          // scala 跳出 for 循环的方式
          breakLoop.break()
        }
      }
    }

  }

  def isPrime(p:Int):Boolean = {
    if (p % 6 == 1 || p % 6 == 5) {
      for (i <- 5.to(math.sqrt(p).toInt, 6)) {
        // p % 从 5 开始 步长为 6 最大值为 math.sqrt(p) 的数列中所有的数，如果都不等于0，就要判断下一个条件，对从7 开始的那个数列
        // p % 从 7 开始 步长为 6 最大值为 math.sqrt(p) 的数列中所有的数，如果都不等于0，就说明这数是素数
        if (p % i == 0 || p % (i + 2) == 0)
          return false
      }
    }else {
      // 这里一定要有这个，否则 6x+2,6x+3,6x+4 都会被认为是素数
      return false
    }
    true
  }
}
